CODE 89. Wildcard Matching

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/27/2013-10-27-CODE 89 Wildcard Matching/
访问原文「CODE 89. Wildcard Matching」

Implement wildcard pattern matching with support for '?' and '*'.
‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 public boolean isMatch(String s, String p) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	if ((null == s && p != null) || (null != s && null == p)) {
		return false;
	} else if (null == s && null == p) {
		return true;
	}
	int plenNoStar = 0;
	for (char c : p.toCharArray())
		if (c != '*')
			plenNoStar++;
	if (plenNoStar > s.length())
		return false;
	
	boolean[] match = new boolean[s.length() + 1];
	int firstTrue = 0;
	match[0] = true;
	
	int lens = s.length();
	int lenp = p.length();
	char[] ss = s.toCharArray();
	char[] ps = p.toCharArray();
	
	for (int i = 0; i < lenp; i++) {
		if (i > 0 && ps[i] == '*' && ps[i - 1] == '*') {
			continue;
		}
		if (ps[i] == '*') {
			for (int fi = firstTrue + 1; fi <= s.length(); ++fi) {
				match[fi] = true;
			}
		} else {
			int firstMatch = -1;
			for (int j = lens; j > firstTrue; j--) {
				if (ss[j - 1] == ps[i] || ps[i] == '?') {
					match[j] = match[j - 1];
				} else {
					match[j] = false;
				}
				if (match[j]) {
					firstMatch = j;
				}
			}
			if (firstMatch < 0) {
				return false;
			} else {
				firstTrue = firstMatch;
			}
		}
	}
	return match[lens];
}